◀ Prev · Parts · Full · Next ▶

Randomness can be viewed as a resource, like space and time. Derandomization is then the process of removing randomness (or using as little of it as possible).cite-ref-21[21]cite-ref-22[22] It is not currently known if all algorithms can be derandomized without significantly increasing their running time.cite-ref-2-23-0[23] For instance, in computational complexity, it is unknown whether P = BPP,cite-ref-2-23-1[23] i.e., we do not know whether we can take an arbitrary randomized algorithm that runs in polynomial time with a small error probability and derandomize it to run in polynomial time without using randomness.

There are specific methods that can be employed to derandomize particular randomized algorithms:

• the method of conditional probabilities, and its generalization, pessimistic estimators

• discrepancy theory (which is used to derandomize geometric algorithms)

◀ Prev · Parts · Full · Next ▶